Esercitazione 2

Esercizio 2.1: esercizio d'esame 2025-09-09

Vediamo ora un esercizio d'esame, del 09 Settembre 2025 (l'ultimo appello). Il testo con soluzione si trova qui.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

L'esercizio ci chiede di

• Leggere un numero di 4 cifre in base 7
• Stamparlo in notazione decimale (base 10)
• Testare e stampare se è divisibile per 64, senza usare div

In particolare, ci è chiesto di risolvere il primo punto scrivendo due sottoprogrammi:

• indigit_b7, per la lettura di una cifra in base 7,
• innumber_b7, per la lettura di un numero a 4 cifre in base 7.

Per entrambi, dovremo gestire l'input ignorando caratteri inattesi: cioè, il programma deve comportarsi come se non fosse stato premuto niente, non stampando nulla e restando in attesa di un carattere corretto (in questo caso, un numero da $0$ a $6$).

Richiami su sottoprogrammi

Partiamo da cosa significa scrivere un sottoprogramma. Un sottoprogramma è un blocco di istruzioni riutilizzabile: si entra nel sottoprogramma con una call e, alla fine di questo, tramite ret si ritorna al chiamante riprendendo dall'istruzione successiva alla call. È infatti questo il meccanismo che sfruttiamo quando utilizziamo i sottoprogrammi di utility, come nello snippet che segue.

    ...
    mov $'h', %ah
    mov $'l', %al
    call outchar # chiamata a sottoprogramma
    cmp $'h', %ah
    je ok
    ...

Il sottoprogramma outchar ci dice, nella sua documentazione, che si occupa di stampare il carattere che trova in %al, in questo caso l.

Parte di ciò che rende un sottoprogramma utile è che faccia quello che dice, e non altro: per esempio, da questa lettura della documentazione ci aspettiamo che il contenuto di %ah non sia modificato, e che quindi la je avrà sempre successo.

Elenchiamo quindi gli aspetti principali di un sottoprogramma:

1. Ci si entra con una call, si esce con una ret;
2. Ha input e output (registri, memoria, I/O) chiaramente documentati;
3. Non modifica alcun registro, locazione di memoria o I/O al di fuori quanto documentato.

Quando si vìola il terzo punto si parla di effetti collaterali, che è un errore.

indigit_b7

Cominciamo quindi a delineare la nostra indigit_b7 partendo da la sua struttura e documentazione:

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %al
indigit_b7:
    ...
    ret

Guardiamo ora al requisito di ignorare caratteri inattesi: il sottoprogramma dovrebbe leggere un carattere e controllare se "va bene", se sì lo stampa e continua altrimenti torna a leggere un altro carattere. Questo non è che un ciclo.

Per quanto riguarda il criterio, si tratta di fare un confronto tra caratteri ASCII, dato che i valori sono consecutivi: tutte le cifre tra $0$ e $6$ sono, nella tabella ASCII, tra i valori 0x30 e 0x36.

Riassiumiamo vedendo come si farebbe in pseudo-C.

bool continua = true;
char c;
while(continua) {
    c = inchar(); // legge un carattere senza farne eco
    if(c < '0' || c > '6')
        continua = true; // non va bene, ne leggiamo un altro
    else
        continua = false; // va bene
}
outchar(c); // stampa il carattere letto

Traducendo questo loop in assembler, otteniamo:

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %al
indigit_b7:
    # ...
indigit_b7_loop:
    call inchar
    cmp $'0', %al
    jb indigit_b7_loop
    cmp $'6', %al
    ja indigit_b7_loop
    # arrivati qui, il carattere è ok
    call outchar
    # ...
    ret

Adesso abbiamo un carattere tra 0 e 6, dobbiamo convertirlo in un valore tra $0$ e $6$. Ricordiamo infatti che il valore di un carattere ASCII è un byte generalmente diverso da quello che rappresenta, cioè $'0' non è uguale a $0.

Per convertire da uno all'altro, ricordiamo che le rappresentazioni dei caratteri sono ordinate, e quindi possiamo ottenere un indice per differenza: per esempio '1' - '0' = 1. Aggiungendo questa sottrazione, otteniamo:

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %al
indigit_b7:
    # ...
indigit_b7_loop:
    call inchar
    cmp $'0', %al
    jb indigit_b7_loop
    cmp $'6', %al
    ja indigit_b7_loop
    # arrivati qui, il carattere è ok
    call outchar
    sub $'0', %al
    # ...
    ret

Quello che manca è controllare gli effetti collaterali. In questo caso non ce ne sono: le istruzioni di indigit_b7, così come la inchar, sporcano solo %al che è lo stesso registro che utilizziamo per l'output. outchar invece non modifica nessun registro. Quindi, per questo sottoprogramma, non c'è bisogno di aggiungere push e pop.

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %al
indigit_b7:
indigit_b7_loop:
    call inchar
    cmp $'0', %al
    jb indigit_b7_loop
    cmp $'6', %al
    ja indigit_b7_loop
    # arrivati qui, il carattere è ok
    call outchar
    sub $'0', %al
    ret

Perché usare due label per indigit_b7 e indigit_b7_loop?

Nel caso visto sopra è chiaramente una distinzione inutile. Consideriamo però un sottoprogramma leggermente diverso, che usi un altro registro come output, per esempio %bl, senza distinguere le due label. L'usare un altro registro significa che il valore di %al va preservato, usando push e pop.

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %bl
indigit_b7:
    push %ax    # push/pop sono solo da 32 o 16 bit, non 8
    call inchar
    cmp $'0', %al
    jb indigit_b7
    cmp $'6', %al
    ja indigit_b7
    # arrivati qui, il carattere è ok
    call outchar
    sub $'0', %al
    pop %ax
    ret

Questo codice ha un bug: con questa struttura, facciamo una nuova push ogni volta che si inserisce un carattere non riconosciuto. Però, in fondo, si ha solo una pop. Questo significa che si arriva alla ret con lo stack sporco: questo causa crash del programma (se va bene e non si trovano istruzioni nel punto a caso in cui salta).

È quindi una buona regola, per evitare errori difficili da debuggare, distinguere le label di ingresso dei sottoprogrammi dalle label utilizzate per fare cicli.

Arrivati a questo punto, abbiamo il sottoprogramma indigit_b7 che possiamo utilizzare per ottenere da terminale una cifra in base 7, e trovarne il valore (compreso tra $0$ e $6$) in %al.

Possiamo verificarne il funzionamento cominciando a scrivere il resto del programma per testarlo (download).

.include "./files/utility.s"

.data

.text
_main:
    nop
    call indigit_b7
    call newline
    call outdecimal_byte
    ret

# Legge e fa eco, ignorando caratteri inattesi, di una cifra in base 7
# Ne lascia il valore in %al
indigit_b7:
indigit_b7_loop:
    call inchar
    cmp $'0', %al
    jb indigit_b7_loop
    cmp $'6', %al
    ja indigit_b7_loop
    # arrivati qui, il carattere è ok
    call outchar
    sub $'0', %al
    ret

Eseguendo questo programma, otteniamo

PS /mnt/c/reti_logiche/assembler> ./assemble.ps1 ./lezioni/2/2025-09-09-p1.s
PS /mnt/c/reti_logiche/assembler> ./lezioni/2/2025-09-09-p1                 
5
5
PS /mnt/c/reti_logiche/assembler> 

innumber_b7

Passiamo ora a scrivere innumber_b7, per la lettura di un numero a 4 cifre in base 7. Definiamo prima cosa vogliamo che faccia. Sarebbe infatti utile che questo sottoprogramma si occupi di convertire la sequenza di 4 cifre nel numero naturale rappresentato.

Bisogna prima però chiedersi: quanto sarà grande questo naturale, quanti bit servono? Questo si chiama fare il dimensionamento, ed è una parte importante per tutti gli esercizi che toccano l'aritmetica. Il numero naturale più grande che si può scrivere con 4 cifre in base 7 è $7^4 - 1 = 2400$. Quindi non ci basta un registro a 8 bit ($2^8 - 1 = 255$), ma ce ne basta uno a 16 bit ($2^{16} - 1 = 65535$).

# Legge e fa eco, ignorando caratteri inattesi, di un numero naturale di 4 cifre in base 7
# Ne lascia il valore in %ax
innumber_b7:
    ...
    ret

Siano $b_3$, $b_2$, $b_1$, $b_0$ le 4 cifre in base 7, ciascuna compresa tra $0$ e $6$. Il numero naturale rappresentato da queste 4 cifre sarà $b_3 \cdot 7^3 + b_2 \cdot 7^2 + b_1 \cdot 7^1 + b_0 \cdot 7^0$. Abbiamo quindi bisogno di

• leggere le 4 cifre (possiamo usare indigit_b7)
• moltiplicare ciascuna cifra per una potenza di 7
• poi sommare questi valori tra di loro. Cominciamo a vedere, in pseudo-C, come potremmo fare questa cosa, ricordandoci che in assembler possiamo fare operazioni aritmetiche (add, mul) solo fra due operandi alla volta.

// per semplicità, il codice che segue non tiene in considerazione i dimensionamenti per le mul...
int b_3 = indigit_b7();
int b_2 = indigit_b7();
int b_1 = indigit_b7();
int b_0 = indigit_b7();

int p_3 = b_3 * 343; // 7*7*7
int p_2 = b_2 * 49; // 7*7
int p_1 = b_1 * 7;
int p_0 = b_0;

int n = ((p3 + p2) + p1 ) + p0;

Questa scomposizione funziona, e potremmo effettivamente tradurla in una implementazione. C'è un vincolo importante, però: dove mettiamo tutte queste variabili intermedie? Ricordiamo che abbiamo sempre 3 opzioni:

• registri
• memoria statica (.data)
• stack

La prima opzione è preferibile (anche per performance) ma i registri sono limitati, e potrebbe essere difficile gestirli. La seconda opzione funziona, ma è la meno elegante: richiede che il sottoprogramma abbia il proprio spazio di memoria dedicato sempre allocato (equivale ad una funzione C che utilizzi variabili globali). La terza opzione è invece la migliore quando si tratta di usare la memoria in sottoprogrammi: non a caso, un compilatore C utilizza per le variabili locali proprio lo stack.

A fini didattici, vediamo prima come fare questo con lo stack. Dobbiamo prima riordinare le operazioni del nostro pseudo-C per rendere l'idea fattibile. Attenzione: possiamo riordinare i calcoli, ma non l'ordine di input, perché l'utente scriverà sempre il numero partendo dalla cifra più significativa.

push e pop non a 8 bit

Ricordiamo che le istruzioni push e pop supportano solo operandi a 16 e 32 bit, non 8. Dobbiamo quindi estendere su almeno 16 bit per utilizzare lo stack.

// per semplicità, il codice che segue non tiene in considerazione i dimensionamenti per le mul...

// fase 1: calcolo prodotti e push
al = indigit_b7();
ax = al * 343;  
push(ax);

al = indigit_b7();
ax = al * 49;
push(ax);

al = indigit_b7();
ax = al * 7;
push(ax);

al = indigit_b7();
ax = al;
push(ax);

// fase 2: pop e sommatoria
ax = 0;
// b_0
bx = pop();
ax += bx;
// += b_1 * 7
bx = pop();
ax += bx;
// += b_2 * 7 * 7
bx = pop();
ax += bx;
// += b_3 * 7 * 7 * 7
bx = pop();
ax += bx;

Per tradurre questo in assembler, dobbiamo risolvere i problemi di dimensionamento per utilizzare correttamente la mul. Infatti, la mul a 8 bit accetta operandi a 8 bit, lasciando un risultato a 16 bit in %ax. La mul a 16 bit accetta operandi a 16 bit, lasciando un risultato a 32 bit in %dx_%ax.

Noi però vogliamo moltiplicare, ad un certo punto, per $343$, che non sta su 8 bit ($> 255$). Quello che dobbiamo fare, almeno per quel passaggio, è quindi utilizzare la mul a 16 bit ignorando la parte alta del risultato in %dx (sappiamo, per dimensionamento, che sarà 0x0000).

Utilizzare costanti quando possibile

In questo esercizio abbiamo potenze di 7, come $7^3$. Si potrebbe pensare di calcolare questo nel programma, con una serie di mul. Sarebbe però uno sforzo del tutto inutile, sia in termini di codice che di cicli del processore.

Se infatti possiamo calcolare in anticipo il risultato (la calcolatrice si può usare) è meglio scriverlo direttamente come costante nel codice, e usare i commenti per dire qual'è il calcolo che vi sta dietro.

# Legge e fa eco, ignorando caratteri inattesi, di un numero naturale di 4 cifre in base 7
# Ne lascia il valore in %ax
innumber_b7:
    # push dei registri sporcati
    push %bx
    push %dx    # sporcato dalla mul a 16 bit

    # fase 1: calcolo prodotti e push
    call indigit_b7
    mov $0, %ah
    mov $343, %bx
    mul %bx
    push %ax

    call indigit_b7
    mov $49, %bl
    mul %bl
    push %ax

    call indigit_b7
    mov $7, %bl
    mul %bl
    push %ax

    call indigit_b7
    mov $0, %ah
    push %ax

    # fase 2: pop e sommatoria
    mov $0, %ax
    # b_0
    pop %bx
    add %bx, %ax
    # += b_1 * 7
    pop %bx
    add %bx, %ax
    # += b_2 * 7 * 7
    pop %bx
    add %bx, %ax
    # += b_3 * 7 * 7 * 7
    pop %bx
    add %bx, %ax

    # pop dei registri sporcati
    pop %dx
    pop %bx

    ret

Questa implementazione del sottoprogramma è la migliore? No. Però funziona, cosa che è l'obiettivo principale da raggiungere.

Infatti, possiamo verificarlo con un programma di test (download). Notiamo che, visto che il risultato è un naturale su 16 bit, ci basterà usare outdecimal_word per stamparne la rappresentazione decimale.

Versione senza stack

Il sottoprogramma scritto sopra utilizza lo stack per gestire i quattro valori intermedi da calcolare e, infine, sommare. Questa tecnica è utile in generale, soprattutto per conti più complessi che richiedono molte più istruzioni (e registri) per ciascun passaggio intermedio.

Tuttavia, è facile osservare che questo calcolo non è così complesso. Infatti, potremmo usare un altro registro come appoggio per calcolare la somma mentre leggiamo nuove cifre, senza passare per lo stack.

# Legge e fa eco, ignorando caratteri inattesi, di un numero naturale di 4 cifre in base 7
# Ne lascia il valore in %ax
innumber_b7:
    # push dei registri sporcati
    push %bx
    push %cx
    push %dx    # sporcato dalla mul a 16 bit

    # inizializzazione registro d'appoggio
    mov $0, %cx

    call indigit_b7
    mov $0, %ah
    mov $343, %bx
    mul %bx
    add %ax, %cx

    call indigit_b7
    mov $49, %bl
    mul %bl
    add %ax, %cx

    call indigit_b7
    mov $7, %bl
    mul %bl
    add %ax, %cx

    call indigit_b7
    mov $0, %ah
    add %ax, %cx

    # riprendiamo il risultato dal registro d'appoggio
    mov %cx, %ax

    # pop dei registri sporcati
    pop %dx
    pop %cx
    pop %bx

    ret

Qui il programma di test per questa versione.

Versione con loop scalabile

Le versioni sopra hanno un grosso limite: tutti e 4 i casi per le 4 cifre vengono gestiti "a mano". Passare a un numero $n$ di cifre richiederebbe scrivere $n$ blocchi di codice simili, ma con costanti diverse.

Per trovare un'alternativa iterativa dobbiamo partire dalla formula, capendo come trasformarla per renderla iterativa.

$$\begin{align*} & b_3 \cdot 7^3 + b_2 \cdot 7^2 + b_1 \cdot 7^1 + b_0 \\ =~& (b_3 \cdot 7^2 + b_2 \cdot 7 + b_1) \cdot 7 + b_0 \\ =~& ((b_3 \cdot 7 + b_2) \cdot 7 + b_1) \cdot 7 + b_0 \end{align*}$$

Possiamo generalizzare questo per una qualunque base $\beta$ e numero di cifre $n$. Sia $x$ il numero naturale di $n$ cifre in base $\beta$, se aggiungo una cifra a destra, sia questa $b$, ottengo allora il numero naturale $x \cdot \beta + b$.

Riflettendoci, c'è anche un modo più immediato per arrivarci: aggiungere una cifra a destra equivale a fare uno shift a sinistra (base $\beta$) delle cifre che si hanno già, a cui poi sommiamo la nuova cifra.

Possiamo quindi scrivere un algoritmo iterativo che, utilizzando questa espressione, calcola man mano il numero naturale inserito dall'utente. Questo significa però che se almeno una delle moltiplicazioni dovrà essere a 16 bit, allora tutte le mul del ciclo dovranno esserlo.

# Legge e fa eco, ignorando caratteri inattesi, di un numero naturale di 4 cifre in base 7
# Ne lascia il valore in %ax
innumber_b7:
    push %bx
    push %cx
    push %dx # sporcato dalle mul a 16 bit

    mov $0, %bx
    mov $4, %cl;
innumber_b7_loop:
    # check fine ciclo
    cmp $0, %cl
    je innumber_b7_fine
    # shift a sinistra (base 7) del numero letto finora
    mov $7, %ax
    mul %bx
    mov %ax, %bx
    # leggo la nuova cifra e la sommo
    call indigit_b7
    mov $0, %ah
    add %ax, %bx
    # nuova iterazione
    dec %cl
    jmp innumber_b7_loop

innumber_b7_fine:
    mov %bx, %ax
    pop %dx
    pop %cx
    pop %bx

    ret

Da notare che questa versione è non solo più breve, ma anche molto più scalabile. Ci basterà infatti cambiare soltanto il valore con cui inizializziamo %cl e il dimensionamento dei registri utilizzati per supportare altri valori di $n$ diversi da $4$: possiamo gestire fino a 5 cifre base 7 mantenendo il risultato su 16 bit, e fino a 11 cifre base 7 passando a 32 bit.

Qui il programma di test per questa versione.

Divisibilità per 64

Ricapitolando, con i sottoprogrammi indigit_b7, innumber_b7 e outdecimal_word possiamo gestire i primi due punti dell'esercizio.

• ✅ Leggere un numero di 4 cifre in base 7
• ✅ Stamparlo in notazione decimale (base 10)
• ⬜ Testare e stampare se è divisibile per 64, senza usare div

Ci resta da controllare la divisibilità per 64. Chiediamoci intanto usando la div - che ci è preclusa - come avremmo potuto fare. La divisione tra naturali fatta dalla div produce un quoziente ed un resto: potremmo verificare la divisibilità controllando che il resto della divisione per 64 sia 0.

Notiamo però che 64 non è un numero qualunque, ma equivale a $2^6$. In una qualunque base $\beta$, un numero è divisibile per $\beta^{n}$ se le sue $n$ cifre meno significative sono $0$.

Dobbiamo quindi controllare che le $6$ cifre meno significative del nostro numero siano 0. Il modo più efficace per farlo è usare un and con una maschera.

Ricordiamo cosa fa la and con una maschera (valore costante):

• lascia i bit dell'operando invariati in corrispondenza degli 1 nella maschera;
• forza a 0 i bit in corrispondenza degli 0 nella maschera.

Possiamo utilizzare una maschera che forzi a 0 tutti i bit che non ci interessano (nelle posizioni da 15 a 6) e lasci invariati quelli che ci interessano: il risultato sarà 0 solo se i bit che ci interessano sono a 0.

Vediamo degli esempi, per semplicità su 8 bit con $16 = 2^4$ come divisore.

      0110 0000     96 = 6 * 16
  AND 0000 1111
      ---------
  =   0000 0000     0

      0110 0110     102, non divisibile per 16
  AND 0000 1111
      ---------
  =   0000 0110     != 0

Tornando al nostro caso, cioè 16 bit e $64 = 2^6$ come divisore, la maschera da utilizzare sarà 0x003F.

punto_1:
    call innumber_b7
    call newline
punto_2:
    call outdecimal_word
    call newline
punto_3:
    and $0x003f, %ax
    jz divisibile
non_divisibile:
    mov $'0', %al
    jmp stampa
divisibile:
    mov $'1', %al
stampa:
    call outchar

Il programma completo (utilizzando la versione iterativa di innumber_b7) è scaricabile qui.

Domande a risposta multipla

2025-01-08, domanda 3

var1: .word 0x1020, 0x32ab
var2: .long var1+2
var3: .byte 0x66

Data la dichiarazione di sopra, qual è il contenuto del byte di memoria di indirizzo var2?

1. 0xab
2. 0x32
3. 0x66
4. Nessuna delle precedenti

Risposta

La risposta giusta è la d.

I quattro byte a partire da var2 formano un indirizzo di memoria, calcolato opportunamente dall'assemblatore o chi per lui. Mentre possiamo prevedere a cosa punti tale indirizzo (il byte 0xAB, il meno significativo del secondo elemento di var1) non abbiamo modo di prevedere il valore di tale indirizzo.

2025-06-04, domanda 2

not %bx
not %ax
or %bx,%ax
not %ax

Il codice sopra scritto calcola:

1. L'and di bx e ax
2. L'or di bx e ax
3. Il nor di bx e ax
4. Nessuna delle precedenti

Risposta

La risposta giusta è la a.

Basta ricordare il teorema di De Morgan:

$$\begin{align*} \overline{ \overline{a} + \overline{b} } &= \overline{ \overline{ a \cdot b } } \\ &= a \cdot b \end{align*}$$

Questo si applica per ogni coppia di bit $a$ e $b$, che siano in posizioni corrispondenti di ax e bx. Quindi, per estensione, il codice è equivalente a and %ax, %bx.

2025-02-11, domanda 1

sar %ax
sal %ax
jc dopo

Il codice scritto sopra salta all’etichetta dopo:

1. Sempre
2. Mai
3. Se prima che si iniziasse il MSB di ax valeva 1
4. Nessuna delle precedenti

Risposta

La risposta giusta è la c.

sar sta per shift arithmetic right: è uno shift aritmetico che preserva il segno dell'operando, cioè se il MSB (most significant bit) è 1 allora anche il risultato avrà 1 come MSB.

sal sta per shift arithmetic left: si comporta come lo shift logico (shl) con l'unica aggiunta di settare anche OF se si verifica un cambio di segno. In particolare, come lo shift logico setta CF se il MSB dell'operando è 1.

Dunque, il salto jc (jump if carry) ha successo solo se sal setta CF, cosa che succede solo sar setta il MSB, cosa che succede solo se l'operando originale aveva il MSB a 1.

Da notare che se la prima istruzione fosse stata uno shift logico (shr), la risposta corretta sarebbe stata mai.